Learning a hidden hypergraph is a natural generalization of the classicalgroup testing problem that consists in detecting unknown hypergraph$H_{un}=H(V,E)$ by carrying out edge-detecting tests. In the given paper wefocus our attention only on a specific family $F(t,s,\ell)$ of localizedhypergraphs for which the total number of vertices $|V| = t$, the number ofedges $|E|\le s$, $s\ll t$, and the cardinality of any edge $|e|\le\ell$,$\ell\ll t$. Our goal is to identify all edges of $H_{un}\in F(t,s,\ell)$ byusing the minimal number of tests. We develop an adaptive algorithm thatmatches the information theory bound, i.e., the total number of tests of thealgorithm in the worst case is at most $s\ell\log_2 t(1+o(1))$. We also discussa probabilistic generalization of the problem.
展开▼
机译：学习隐藏的超图是对经典组测试问题的自然概括，该问题包括通过执行边缘检测测试来检测未知的超图$ H_ {un} = H（V，E）$。在给定的论文中，我们仅将注意力集中在特定家庭$ F（t，s，\ ell）$的局部超图上，其总顶点数为$ | V |。 = t $，边的数量$ | E | \ le s $，$ s \ ll t $和任意边的基数$ | e | \ le \ ell $，$ \ ell \ ll t $。我们的目标是通过使用最少的测试来确定F（t，s，\ ell）$中$ H_ {un} \的所有边。我们开发了一种与信息理论范围匹配的自适应算法，即最坏情况下算法的测试总数最多为$ s \ ell \ log_2 t（1 + o（1））$。我们还讨论了该问题的概率概括。
展开▼
